/*
 * @lc app=leetcode.cn id=494 lang=golang
 * @lcpr version=30118
 *
 * [494] 目标和
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func findTargetSumWays(nums []int, target int) int {
	res := 0
	dfs(nums, target, 0, 0, &res)
	return res
}

func dfs(nums []int, target int, sum int, start int, res *int) {
	if target == sum && start == len(nums) {
		(*res)++
		return
	}
	if start >= len(nums) {
		return
	}
	dfs(nums, target, sum+nums[start], start+1, res)
	dfs(nums, target, sum-nums[start], start+1, res)
}

// @lc code=end

/*
// @lcpr case=start
// [1,1,1,1,1]\n3\n
// @lcpr case=end

// @lcpr case=start
// [1]\n1\n
// @lcpr case=end

*/

